class Solution(object):
    def multiply(self, mat1, mat2):
        """
        :type mat1: List[List[int]]
        :type mat2: List[List[int]]
        :rtype: List[List[int]]
        """
        M = len(mat1)
        N = len(mat1[0])
        C = len(mat2[0])
        d1 = {}
        d2 = {}
        out = [[0 for _ in range(C)] for _ in range(M)]
        for i in range(M):
            for j in range(N):
                if mat1[i][j] != 0:
                    if i not in d1:
                        d1[i] = {}
                    d1[i][j] = mat1[i][j]
        for j in range(N):
            for k in range(C):
                if mat2[j][k] != 0:
                    if j not in d2:
                        d2[j] = {}
                    d2[j][k] = mat2[j][k]
        for i in d1:
            for j in d1[i]:
                if j in d2:
                    for c in d2[j]:
                        out[i][c] += d1[i][j] * d2[j][c]
        return out


data = Solution()
mat1 = [[1, 0, 0], [-1, 0, 3]]
mat2 = [[7, 0, 0], [0, 0, 0], [0, 0, 1]]
print(data.multiply(mat1, mat2))
